package com.algorithm.cn.recursion;

/**
 * 
 * @author wangzonghui
 * @date 2021-01-12 20:33:25
 * @Description:8皇后问题代码实现
 */
public class Queue8 {

	int max=8;  //皇后数量
	int[] array =new int[max];//皇后放置位置的结果 {0,4,7,5,2,6,1,3}  index是行，值为列
	static int count=0; //成功次数
	static int judeCount=0;  //失败次数
	
	public static void main(String[] args) {
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.println("总解法数:"+count);
		System.out.println("共判断冲突次数:"+judeCount);
	}
	
	/**
	 * 编写放置第n个皇后
	 * @param n
	 */
	private void check(int n) {
		if(n ==max) {  //8个皇后放好了。
			show();
			return;
		}
		
		//以此放入皇后，并判断是否冲突
		for(int i=0;i<max;i++) {
			//先把当前皇后n，放到该行的第1列
			array[n]=i;
			//判断当放置第n个皇后到i列时，是否冲突
			if(jude(n)) {  //不冲突
				check(n+1);
			}
			//如果冲突继续执行array[n]=i，即将第n个皇后，放置在本行得后移一个位置
		}
	}
	
	/**
	 * 查看当放置第n个皇后时，是否和前面摆放的皇后冲突
	 */
	private boolean jude(int n) {
		judeCount++;
		for(int i=0;i<n;i++) {
			/**
			 * 1、array[i]==array[n] 表示第n个皇后是否和前面n-1皇后时同一列
			 * n=1 放置第2列 1时，n=1 array[1]=1
			 * 2、 Math.abs(n-i)==Math.abs(array[n]-array[i]) 表示第n个皇后和第i皇后是否在同一斜线
			 * Math.abs(n-i)==1  Math.abs(array[n]-array[i])=Math.abs(1-0)=1
			 */
			if(array[i]==array[n] || Math.abs(n-i)==Math.abs(array[n]-array[i])) {  //同行 斜线冲突   
				return false;
			}
		}
		return true;
	}
	
	
	/**
	 * 写一个方法，可以将皇后摆放的位置打印出来
	 */
	private void show() {
		count++;
		for(int i=0,size=array.length;i<size;i++) {
			System.out.print(array[i]+" ");
		}
		System.out.println();
	}

}
